一、DANE [2018]

《Deep Attributed Network Embedding》

1. 网络在现实世界中无处不在，例如社交网络、学术引用网络、通信网络。在各种网络中，属性网络（attributed network） 近年来备受关注。与仅有拓扑结构可用的普通网络（plain network）不同，属性网络的节点拥有丰富的属性信息，并有利于网络分析。例如，在学术引用网络中，不同文章之间的引用构成了一个网络，其中每个节点都是一篇文章，每个节点都有关于文章主题的、大量的文本信息。另一个例子是社交网络，用户之间可以相互联系，并且每个用户节点都有个性化的用户画像属性信息。此外，社会科学表明：节点的属性可以反映和影响其社区结构。因此，研究属性网络是必要且重要的。

   network embedding 作为分析网络的基本工具，最近在数据挖掘和机器学习社区引起了极大的关注。network embedding 在保持邻近性的同时为每个节点学习低维 representation。然后，下游任务（如节点分类、链接预测、网络可视化）可以从学到的低维 representation 中获益。近年来，人们已经提出了各种 network embedding 方法，如 DeepWalk, Node2Vec, LINE。然而，大多数现有的方法主要关注普通网络，忽略了节点的有用属性。例如，在 Facebook 或 Twitter 等社交网络中，每个用户都与其它用户连接，从而构成一个网络。大多数现有的方法在学习 node representation 时仅关注连接。但是每个节点的属性也可以提供有用的信息。一个很好的例子是用户画像。一名年轻用户可能与另一名年轻用户具有更多的相似性，而与年长用户不太相似。因此，在学习 node representation 时结合节点属性很重要。

   另外，网络的拓扑结构和节点属性是高度非线性的。因此，捕获高度非线性的特性从而发现底层模式underlying pattern 非常重要。然后，就可以在学到的 node representation 中更好地保留邻近性。然而，大多数现有的方法仅采用浅层模型，未能捕获到高度非线性的特性。此外，由于复杂的拓扑结构和节点属性，很难捕获这种高度非线性的特性。因此，捕获属性网络 embedding 的高度非线性特性是一项挑战。

   为解决上述问题，论文《Deep Attributed Network Embedding》提出了一种用于属性网络的、新颖的 deep attributed network embedding: DANE 方法。具体而言，论文提出了一个深度模型来同时捕获网络拓扑结构和节点属性中底层的高度非线性。同时，所提出的模型可以迫使学到的 node representation 保持原始网络中的一阶邻近性和高阶邻近性。此外，为了从网络的拓扑结构和节点属性中学习一致（consistent） 的和互补（complementary ）的 representation，论文提出了一种同时结合这两种信息的新策略。另外，为了获得鲁棒的 node representation，论文提出了一种有效的 “最负采样” （most negative sampling）策略来使得损失函数更鲁棒。最后，论文进行了大量的实验来验证所提出方法的有效性。

2. 相关工作：

   • 普通网络 embedding：network embedding 可以追溯到 graph embedding 问题，如 Laplacian Eigenmaps、LPP。这些方法在保持局部流形结构（local manifold structure ）的同时学习数据 embedding 。然而，这些方法不适用于大型网络 embedding，因为它们涉及耗时的 eigen-decomposition 操作，其时间复杂度为 $O(n^3)$$O(n^3)$，$n$$n$ 为节点数量。

     最近，随着大型网络的发展，很多 network embedding 纷纷出现。例如：

     • DeepWalk采用截断的随机游走和 SkipGram 来学习 node representation。该方法基于以下观察：随机游走中节点的分布与自然语言中的单词分布很相似。

     • LINE 提出在学习节点representation 时保持一阶邻近性和二阶邻近性。

     • GraRep 在 LINE 的基础上进一步提出保持高阶邻近性。

     • Node2Vec 提出通过一个有偏 （biased ）的随机游走来得到灵活的邻域概念。

     然而，所有这些方法都仅利用了拓扑结构，而忽略了节点的有用属性。

   • 属性网络 embedding ：近年来，属性网络 embedding 引起了广泛的关注。人们已经为属性网络提出了各种各样的模型。

     • TADW 提出了一种 inductive 的矩阵分解方法来结合网络拓扑结构和节点属性。然而，它本质上是一个线性模型，对于复杂的属性网络而言是不够的。

     • AANE 和 LANE 采用图拉普拉斯（graph Laplacian）技术从网络拓扑结构和节点属性中学习联合 embedding 。

     • 《Semi-supervised classification with graph convolutional networks》提出了一种用于属性网络的图卷积神经网络模型。但是，这个模型仅是一种半监督方法，无法处理无监督的情况。

     • 《Tri-party deep network representation》 提出将 DeepWalk 与神经网络结合起来用于 network representation 。尽管如此，DeepWalk 部分仍然是一个浅层模型。

     • 最近，人们提出了两种无监督的深度属性网络 embedding 方法：《Variational graph auto-encoders》、《Inductive representation learning on large graphs》。但是它们仅能隐式地探索拓扑结构。

     因此，有必要以更有效的方式探索深度属性网络 embedding 方法。

1.1 模型

1.1.1 基本概念

1. 令 $G=(\mathcal{V},\mathcal{E},\mathbf{X})$$G=(\mathcal V,\mathcal E,\mathbf X)$ 为一个属性信息网络，其中：

   • $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n\}$ 为节点集合，$\mathcal{E}$$\mathcal E$ 为边的集合。

   • $\mathbf{X}\in {\mathbb{R}}^{n\times m}$$\mathbf X\in \mathbb R^{n\times m}$ 为节点的属性集合，${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^m$$\mathbf{\vec x}_i\in \mathbb R^m$ 为 $\mathbf{X}$$\mathbf X$ 的第 $i$$i$ 行，表示节点 $v_i$$v_i$ 的特征向量。

   • $\mathbf{E}\in {\mathbb{R}}^{n\times n}$$\mathbf E\in \mathbb R^{n\times n}$ 为邻接矩阵，如果 $v_i,v_j$$v_i,v_j$ 之间存在边则 $e_{i,j}>0$$e_{i,j} \gt 0$ ；如果 $v_i,v_j$$v_i,v_j$ 之间没有边则 $e_{i,j}=0$$e_{i,j} = 0$ 。

2. 一阶邻近性定义：给定一个网络 $G=(\mathcal{V},\mathcal{E},\mathbf{X})$$G=(\mathcal V,\mathcal E,\mathbf X)$，定义节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的一阶邻近性（ first-order proximity ）为 $e_{i,j}$$e_{i,j}$ 。如果 $e_{i,j}$$e_{i,j}$ 越大则说明节点 $v_i$$v_i$ 和 $v_j$$v_j$ 关系越紧密。

   一阶邻近性表示：如果两个节点之间存在链接则它们是相似的，否则它们是不相似的。因此，可以将一阶邻近性视为局部邻近性（local proximity） 。

3. 高阶邻近性定义：给定一个网络 $G=(\mathcal{V},\mathcal{E},\mathbf{X})$$G=(\mathcal V,\mathcal E,\mathbf X)$，定义节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的 $k$$k$ 阶邻近性为：$\text{sim}({\overrightarrow{\mathbf{m}}}_i^{(k)},{\overrightarrow{\mathbf{m}}}_j^{(k)})$$\text{sim}\left(\mathbf{\vec m}_i^{(k)},\mathbf{\vec m}_j^{(k)}\right)$ 。其中：

   • $\hat{\mathbf{E}}\in {\mathbb{R}}^{n\times n}$$\hat{\mathbf E}\in \mathbb R^{n\times n}$ 为节点之间的一阶转移概率矩阵，它就是将 $\mathbf{E}$$\mathbf E$ 进行行归一化的矩阵。

     $\hat{\mathbf{E}}$$\hat{\mathbf E}$ 的第 $i$$i$ 行刻画了节点 $v_i$$v_i$ 经过单步转移到其它节点的概率。

   • ${\hat{\mathbf{E}}}^k=\underset{k}{\underbrace{\hat{\mathbf{E}}\cdots \hat{\mathbf{E}}}}\in {\mathbb{R}}^{n\times n}$$\hat{\mathbf E}^k = \underbrace{\hat{\mathbf E}\cdots\hat{\mathbf E}}_k \in \mathbb R^{n\times n}$ 为节点之间的 $k$$k$ 阶概率转移矩阵。

     ${\hat{\mathbf{E}}}^k$$\hat{\mathbf E}^k$ 的第 $i$$i$ 行刻画了节点 $v_i$$v_i$ 经过 $k$$k$ 步转移到其它节点的概率。

   • ${\mathbf{M}}^{(k)}=\hat{\mathbf{E}}+{\hat{\mathbf{E}}}^2+\cdots +{\hat{\mathbf{E}}}^k\in {\mathbb{R}}^{n\times n}$$\mathbf M^{(k)} = \hat{\mathbf E} + \hat{\mathbf E}^2 +\cdots+\hat{\mathbf E}^k\in \mathbb R^{n\times n}$ 为 $G$$G$ 的 $k$$k$ 阶邻近性矩阵（proximity matrix） 。${\overrightarrow{\mathbf{m}}}_i^{(k)}\in {\mathbb{R}}^n$$\mathbf{\vec m}_i^{(k)}\in \mathbb R^{n }$ 为 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ 的第 $i$$i$ 行。

     ${\overrightarrow{\mathbf{m}}}_i^{(k)}$$\mathbf{\vec m}_i^{(k)}$ 刻画了节点 $v_i$$v_i$ 在 $k$$k$ 步之内转移到其它节点的概率。

   • $\text{sim}(\cdot )$$\text{sim}(\cdot)$ 为向量的相似度函数（如余弦相似度）。

   高阶邻近性（high-order proximity）刻画了节点之间的邻域相似性。具体来讲：如果两个节点共享相同的邻域则它们是相似的，否则是不相似的。因此，高阶邻近性可以视为全局邻近性。

4. 语义邻近性定义：给定一个网络 $G=(\mathcal{V},\mathcal{E},\mathbf{X})$$G=(\mathcal V,\mathcal E,\mathbf X)$，定义节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的语义邻近性（ semantic proximity）为：$\text{sim}({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j)$$\text{sim}(\mathbf{\vec x}_i , \mathbf{\vec x}_j)$ 。其中： $\text{sim}(\cdot )$$\text{sim}(\cdot)$ 为向量的相似度函数（如余弦相似度），${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^m$$\mathbf{\vec x}_i\in \mathbb R^{m}$ 为节点 $v_i$$v_i$ 的属性向量。

5. 属性网络representation learning 任务的目标是学习一个映射函数 $f:v_i\to {\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^d$$f: v_i\rightarrow \mathbf{\vec h}_i \in \mathbb R^d$ ，其中 $d\ll n$$d\ll n$ ，它将每个节点 $v_i$$v_i$ 映射到一个低维向量 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ ，并在映射过程中保持网络结构邻近性（包括一阶邻近性、高阶邻近性）、节点属性邻近性。

1.1.2 DANE

1. 属性网络embedding 面临三大挑战：

   • 高度非线性：网络拓扑结构和节点属性的底层结构都是高度非线性的，这种高度非线性很难捕获。

   • 邻近性保持：属性网络的邻近性取决于网络拓扑结构和节点属性，如何挖掘和保持邻近性关系是一个难点。

   • 信息的一致性（consistent）和互补性（complementary）：网络拓扑结构和节点属性这两种信息源为每个节点提供了不同的视角，二者是是一致的（都能刻画节点之间的关系）、互补的（包含对方没有的信息）。因此，学到的节点embedding 同时编码这两种信息的一致性、互补性非常重要。

   为了解决这三个挑战，我们开发了一种新颖的 deep attributed network embedding: DANE 方法。DANE 利用深度神经网络分别捕获网络结构的非线性、节点属性的非线性来解决这些问题，整体架构如下。DANE 有两个分支：

   • 第一个分支捕获高度非线性的网络结构，从而将输入 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ 映射到低维空间。

   • 第二个分支捕获高度非线性的节点属性，从而将输入 $\mathbf{X}$$\mathbf X$ 映射到低维空间。

   这两路分支都采用深度非线性网络组成，从而捕获数据中的非线性关系。

   模型的算法复杂度为 $O(n^2)$$O(n^2)$，因此无法应用于大型网络。

   

2. 高度非线性：为捕获数据中的高度非线性，DANE 中的每一路分支都是一个自编码器。自编码器是用于 feature learning 的强大无监督深度模型。基本的自编码器包含三层，分别为输入层、隐层、输出层：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i=\sigma ({\mathbf{W}}^{(1)}{\overrightarrow{\mathbf{x}}}_i+{\overrightarrow{\mathbf{b}}}^{(1)})\\ {\widehat{\overrightarrow{\mathbf{x}}}}_i=\sigma ({\mathbf{W}}^{(2)}{\overrightarrow{\mathbf{h}}}_i+{\overrightarrow{\mathbf{b}}}^{(2)})\end{array}$$

   其中：${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^n$$\mathbf{\vec x}_i\in \mathbb R^n$ 为第 $i$$i$ 个输入数据，${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^{n^{\prime }}$$\mathbf{\vec h}_i\in \mathbb R^{n^\prime}$ 为编码器的hidden representation，${\widehat{\overrightarrow{\mathbf{x}}}}_i\in {\mathbb{R}}^n$$\hat{\mathbf{\vec x}}_i\in \mathbb R^n$ 为解码器重构的输出，$\theta =\{{\mathbf{W}}^{(1)},{\overrightarrow{\mathbf{b}}}^{(1)},{\mathbf{W}}^{(2)},{\overrightarrow{\mathbf{b}}}^{(2)}\}$$\theta=\left\{\mathbf W^{(1)},\mathbf{\vec b}^{(1)},\mathbf W^{(2)},\mathbf{\vec b}^{(2)}\right\}$ 为模型参数，$\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数。

   自编码器的目标是最小化重构误差：

   $$\underset{\theta }{min}\sum _{i=1}^N{\Vert {\widehat{\overrightarrow{\mathbf{x}}}}_i-{\overrightarrow{\mathbf{x}}}_i\Vert }_2^2$$

   其中 $N$$N$ 为训练集的大小。

   为捕获网络拓扑结构和节点属性中的高度非线性，DANE 使用了 $L$$L$ 层的编码器（相应地，解码器也有 $L$$L$ 层）：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i^{(1)}=\sigma ({\mathbf{W}}^{(1)}{\overrightarrow{\mathbf{x}}}_i+{\overrightarrow{\mathbf{b}}}^{(1)})\\ \cdots \\ {\overrightarrow{\mathbf{h}}}_i^{(L)}=\sigma ({\mathbf{W}}^{(L)}{\overrightarrow{\mathbf{x}}}_i+{\overrightarrow{\mathbf{b}}}^{(L)})\end{array}$$

   其中编码器的第 $L$$L$ 层输出就是我们想要的节点 embedding ：${\overrightarrow{\mathbf{h}}}_i={\overrightarrow{\mathbf{h}}}_i^{(L)}$$\mathbf{\vec h}_i = \mathbf{\vec h}_i^{(L)}$ 。

   在 DANE 中：

   • 第一路分支的输入是高阶邻近矩阵 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ 用于捕获网络拓扑结构中的非线性，学到的embedding 记作 ${\mathbf{H}}^{<M>}$$\mathbf H^{<M>}$ 。

   • 第二路分支的输入是节点属性矩阵 $\mathbf{X}$$\mathbf X$ 用于捕获节点属性中的非线性，学到的 embedding 记作 ${\mathbf{H}}^{<X>}$$\mathbf H^{<X>}$ 。

3. 邻近性保持：属性网络中存在三种类型的邻近性，语义邻近性（semantic proximity） 、高阶邻近性（high-order proximity） 、一阶邻近性 （first-order proximity）。

   • 为保持语义邻近性，我们最小化编码器输入 $\mathbf{X}$$\mathbf X$ 和解码器输出 $\hat{\mathbf{X}}$$\hat{\mathbf X}$ 的重构误差：

     $${\mathcal{L}}_s=\sum _{i=1}^n{\Vert {\widehat{\overrightarrow{\mathbf{x}}}}_i-{\overrightarrow{\mathbf{x}}}_i\Vert }_2^2$$

     原因在 《Semantic hashing》 中披露。具体而言，重建损失可以强迫神经网络平滑地捕获数据流形，从而可以保持样本之间的邻近性。因此，通过最小化重建损失，我们的方法可以保持节点属性中的语义邻近性。

   • 为了保持高阶邻近性，我们最小化编码器输入 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ 和解码器输出 ${\hat{\mathbf{M}}}^{(k)}$$\mathbf{\hat M}^{(k)}$ 的重构误差：

     $${\mathcal{L}}_h=\sum _{i=1}^n{\Vert {\widehat{\overrightarrow{\mathbf{m}}}}_i-{\overrightarrow{\mathbf{m}}}_i\Vert }_2^2$$

     具体而言，高阶邻近性 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ 刻画了邻域结构。如果两个节点具有相似的邻域结构（即 ${\overrightarrow{\mathbf{m}}}_i^{(k)}$$\mathbf{\vec m}_i^{(k)}$ 和 ${\overrightarrow{\mathbf{m}}}_j^{(k)}$$\mathbf{\vec m}_j^{(k)}$ 是相似的），则通过最小化重建损失学到的 representation 也将彼此相似。

   • 一阶邻近性捕获了局部结构，因此我们也需要捕获一阶邻近性。根据一阶邻近性的定义，如果两个节点之间存在边则它们是相似的。为保持这种邻近性，我们最大化对数似然： $\prod _{e_{i,j}>0}{p}_{i,j}$$\prod_{e_{i,j}\gt 0} p_{i,j}$ ，其中 $p_{i,j}$$p_{i,j}$ 为节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的联合概率。

     注意，我们需要同时保留网络拓扑结构的一阶邻近性和节点属性的一阶邻近性，以便我们可以从这两种不同来源的信息中间取得一致的结果。

     对于网络拓扑结构，节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的联合概率定义为：

     $$p_{i,j}^{<M>}=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{h}}}_i^{<M>}\cdot {\overrightarrow{\mathbf{h}}}_j^{<M>})}$$

     类似地，对于节点属性，节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的联合概率定义为：

     $$p_{i,j}^{<X>}=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{h}}}_i^{<X>}\cdot {\overrightarrow{\mathbf{h}}}_j^{<X>})}$$

     因此我们定义以下目标函数从而来同时保持网络拓扑结构的一阶邻近性和节点属性的一阶邻近性：

     $${\mathcal{L}}_f=-\sum _{e_{i,j}>0}\log p_{i,j}^{<M>}-\sum _{e_{i,j}>0}\log p_{i,j}^{<X>}$$

4. 一致性、互补性的 embedding ：网络拓扑结构和节点属性是同一个网络的两种不同模态的信息，因此我们应该确保从它们中学到的embedding 是一致（consistent） 的，即一致性。另一方面，这两种信息描述了同一个节点的不同方面，提供了互补的信息，因此学到的emedding 应该是互补（complementary ）的，即互补性。

   融合两种形式的 embedding ${\mathbf{H}}^{<M>}$$\mathbf H^{<M>}$ 和 ${\mathbf{H}}^{<X>}$$\mathbf H^{<X>}$ 最简单直接的方式是将它们拼接起来作为节点的最终 embedding 。这种方式可以使得两种模式的 embedding 之间信息互补，但是无法确保它们之间是一致的。

   一致性指的是：${\overrightarrow{\mathbf{h}}}_i^{<M>}\cdot {\overrightarrow{\mathbf{h}}}_j^{<M>}\simeq {\overrightarrow{\mathbf{h}}}_i^{<X>}\cdot {\overrightarrow{\mathbf{h}}}_j^{<X>}$$\mathbf{\vec h}_{i}^{<M>}\cdot \mathbf{\vec h}_{j}^{<M>}\simeq \mathbf{\vec h}_{i}^{<X>}\cdot \mathbf{\vec h}_{j}^{<X>}$ ，互补性指的是 ${\overrightarrow{\mathbf{h}}}_i^{<M>}\ne {\overrightarrow{\mathbf{h}}}_i^{<X>}$$\mathbf{\vec h}_{i}^{<M>}\ne \mathbf{\vec h}_{i}^{<X>}$

   另一种融合的方式是：强制DANE 的两个分支采用共享的最高编码层，即 ${\mathbf{H}}^{<M>}={\mathbf{H}}^{<X>}$$\mathbf H^{<M>} = \mathbf H^{<X>}$ 。尽管这确保两种模态的 embedding 之间是一致的，但是丢失了大量的互补信息。因此，对于属性网络 embedding，如何将网络拓扑结构和节点属性结合在一起是一个具有挑战性的问题。

   为了得到一致的、互补的 embedding，我们提出最大化以下似然估计：

   $$\prod _{i,j}^n{q}_{i,j}^{s_{i,j}}(1-q_{i,j}{)}^{1-s_{i,j}}$$

   其中：

   • $q_{i,j}$$q_{i,j}$ 是两个模态之间的联合分布：

     $$q_{i,j}=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{h}}}_i^{<M>}\cdot {\overrightarrow{\mathbf{h}}}_j^{<X>})}$$

   • $s_{i,j}\in \{0,1\}$$s_{i,j}\in \{0,1\}$ 描述了 ${\overrightarrow{\mathbf{h}}}_i^{<M>}$$\mathbf{\vec h}_i^{<M>}$ 和 ${\overrightarrow{\mathbf{h}}}_j^{<X>}$$\mathbf{\vec h}_j^{<X>}$ 是否来自于同一个节点，即：

     $$\begin{array}{c}{s}_{i,j}=\{\begin{array}{ll}1,& i=j\\ 0,& i\ne j\end{array}\end{array}$$

   因此我们定义损失函数：

   $${\mathcal{L}}_c=-\sum _i[\log q_{i,i}-\sum _{j\ne i}\log (1-q_{i,j})]$$

   通过最小化该损失函数，我们可以强制 ${\overrightarrow{\mathbf{h}}}_i^{<M>}$$\mathbf{\vec h}_i^{<M>}$ 和 ${\overrightarrow{\mathbf{h}}}_j^{<X>}$$\mathbf{\vec h}_j^{<X>}$ ：

   • 当它们来自于同一个节点时，尽可能地一致。但是它们又不完全相同，因此可以提供互补的信息。

   • 当它们来自于不同节点时，尽可能推开。

   但是上述损失函数的第二项过于严格。例如，如果两个节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间存在链接，则根据一阶邻近性它们是相似的。因此尽管 $v_i$$v_i$ 和 $v_j$$v_j$ 是不同的节点， ${\overrightarrow{\mathbf{h}}}_i^{<M>}$$\mathbf{\vec h}_i^{<M>}$ 和 ${\overrightarrow{\mathbf{h}}}_j^{<X>}$$\mathbf{\vec h}_j^{<X>}$ 应该相似。即，我们不应该将它们的 embedding 推开。因此我们放松条件为：

   $${\mathcal{L}}_c=-\sum _i[\log q_{i,i}-\sum _{e_{i,j}=0}\log (1-q_{i,j})]$$

   即：

   • 当节点 $i=j$$i=j$ 时，强制 ${\overrightarrow{\mathbf{h}}}_i^{<M>}$$\mathbf{\vec h}_i^{<M>}$ 和 ${\overrightarrow{\mathbf{h}}}_j^{<X>}$$\mathbf{\vec h}_j^{<X>}$ 尽可能一致。

   • 当 $i\ne j$$i\ne j$ 且 $v_i,v_j$$v_i,v_j$ 之间没有链接时，强制 ${\overrightarrow{\mathbf{h}}}_i^{<M>}$$\mathbf{\vec h}_i^{<M>}$ 和 ${\overrightarrow{\mathbf{h}}}_j^{<X>}$$\mathbf{\vec h}_j^{<X>}$ 推开。

5. 为了保持节点之间的邻近性（三种类型的邻近性），并学习一致和互补的 embedding，DANE 共同优化了目标函数：

   $$\begin{array}{c}\mathcal{L}={\mathcal{L}}_f+{\mathcal{L}}_s+{\mathcal{L}}_h+{\mathcal{L}}_c\\ =-\sum _{e_{i,j}>0}\log p_{i,j}^{<M>}-\sum _{e_{i,j}>0}\log p_{i,j}^{<X>}+\sum _{i=1}^n{\Vert {\widehat{\overrightarrow{\mathbf{x}}}}_i-{\overrightarrow{\mathbf{x}}}_i\Vert }_2^2\\ +\sum _{i=1}^n{\Vert {\widehat{\overrightarrow{\mathbf{m}}}}_i-{\overrightarrow{\mathbf{m}}}_i\Vert }_2^2-\sum _i[\log q_{i,i}-\sum _{e_{i,j}=0}\log (1-q_{i,j})]\end{array}$$

   通过最小化该目标函数，我们获得了 ${\mathbf{H}}^{<M>}$$\mathbf H^{<M>}$ 和 ${\mathbf{H}}^{<X>}$$\mathbf H^{<X>}$ 。我们将二者的拼接作为节点的最终低维 representation，从而可以从网络拓扑结构和节点属性中保留一致、互补的信息。

   理论上可以利用超参数来平衡不同损失函数的重要性：$\mathcal{L}={\mathcal{L}}_f+{\alpha }_1\times {\mathcal{L}}_s+{\alpha }_2\times {\mathcal{L}}_h+{\alpha }_3\times {\mathcal{L}}_c$$\mathcal L = \mathcal L_f+ \alpha_1\times \mathcal L_s + \alpha_2\times \mathcal L_h +\alpha_3\times \mathcal L_c$

1.1.3 最负采样策略

1. 考虑损失函数 ${\mathcal{L}}_c$$\mathcal L_c$，它等价于对每个节点 $v_i$$v_i$ 优化损失：

   $${\mathcal{L}}_{c_i}=-\log q_{i,i}-\sum _{j,e_{i,j}=0}\log (1-q_{i,j})$$

   实际应用中，很多链接由于各种原因未能观测到，所以邻接矩阵 $\mathbf{E}$$\mathbf E$ 非常稀疏。但是，未观测到的链接并不意味着两个节点不相似。如果我们推开两个潜在的相似节点，则学到的embedding 效果会较差。

   具体而言，假设当前节点为 $v_i$$v_i$ ，对于 $e_{i,j}=0$$e_{i,j} =0$ 的节点 $v_j$$v_j$ 我们有：

   $${\mathrm{\nabla }}_{{\overrightarrow{\mathbf{h}}}_j^{<M>}}{\mathcal{L}}_{c_i}=q_{i,j}{\overrightarrow{\mathbf{h}}}_i^{<X>}$$

   因此参数 ${\overrightarrow{\mathbf{h}}}_j^{<M>}$$\mathbf{\vec h}_j^{<M>}$ 的更新规则为 ${\overrightarrow{\mathbf{h}}}_j^{<M>}\leftarrow {\overrightarrow{\mathbf{h}}}_j^{<M>}-\alpha q_{i,j}{\overrightarrow{\mathbf{h}}}_i^{<X>}$$\mathbf{\vec h}_j^{<M>}\leftarrow \mathbf{\vec h}_j^{<M>} - \alpha q_{i,j}\mathbf{\vec h}_i^{<X>}$ ，其中 $\alpha$$\alpha$ 为学习率。

   由于更新过程中 ${\overrightarrow{\mathbf{h}}}_i^{<X>}$$\mathbf{\vec h}_i^{<X>}$ 固定，因此 $q_{i,j}$$q_{i,j}$ 决定了更新后的结果。而 $q_{i,j}$$q_{i,j}$ 依赖于 ${\overrightarrow{\mathbf{h}}}_i^{<M>}\cdot {\overrightarrow{\mathbf{h}}}_j^{<X>}$$\mathbf{\vec h}_i^{<M>} \cdot \mathbf{\vec h}_j^{<X>}$ ：如果两个节点 $v_i$$v_i$ 和 $v_j$$v_j$ 潜在地相似，但是没有观测到链接，则 $q_{i,j}$$q_{i,j}$ 很大。此时，${\overrightarrow{\mathbf{h}}}_j^{<M>}$$\mathbf{\vec h}_j^{<M>}$ 将和 ${\overrightarrow{\mathbf{h}}}_i^{<X>}$$\mathbf{\vec h}_i^{<X>}$ 推得越来越远。结果，embedding 效果越来越差。

   为缓解该问题，我们提出一个最负采样策略来获得更加鲁棒的 embedding 。具体而言，在每次迭代过程中，我们首先计算 ${\mathbf{H}}^{<M>}$$\mathbf H^{<M>}$ 和 ${\mathbf{H}}^{<X>}$$\mathbf H^{<X>}$ 的相似度：

   $$\mathbf{Q}={\mathbf{H}}^{<M>}{\mathbf{H}}^{<X{>}^{\mathrm{\top }}}\in {\mathbb{R}}^{n\times n}$$

   然后对每个节点 $i$$i$ ，我们选择最负most negative 的负样本：

   $$j_i^{\ast }=\arg \underset{j,e_{i,j}=0}{min}{Q}_{i,j}$$

   然后基于这个最负样本，我们设置目标函数为：

   $${\mathcal{L}}_{c_i}=-\log q_{i,i}-\log (1-q_{i,j_i^{\ast }})$$

   采用这种最负采样策略，我们尽可能不违反潜在的相似节点，因此结果更加鲁棒。

   “最负”样本本质上是最可能的“负样本”，这等价于为负样本赋予不同的置信度。

2. 最负采样策略依赖于相似度矩阵 $\mathbf{Q}$$\mathbf Q$，其计算复杂度为 $O(n^2)$$O(n^2)$ 。原始的计算 ${\mathcal{L}}_{c_i}$$\mathcal L_{c_i}$ 的计算复杂度也为 $O(n^2)$$O(n^2)$ ，因为需要遍历所有的 $e_{i,j}=0$$e_{i,j} = 0$ 。这里我们忽略了计算 $q_{i,j}$$q_{i,j}$ 的计算复杂度。

   因此，最负采样策略并没有增加太大的额外开销。

1.2 实验

1. 数据集：

   • 论文引用数据集：我们采用 Cora, Citeseer, PubMed 三个论文引用数据集，边代表论文之间的引用链接，节点的属性为论文的 Bag-Of-Word 表示。

   • Wiki 数据集：维基百科数据集，边代表网页中的超链接，节点的属性为网页内容的 Bag-Of-Word 表示。

   

2. Baseline 方法：为评估DANE 的性能，我们将它与其它几种 baseline 方法进行比较，包括 4 种普通网络的embedding 方法、5 种属性网络embedding 方法。

   • 普通网络embedding 方法：DeepWalk,Node2vec,GraRep,LINE。

   • 属性网络embedding 方法：TADW, ANE, 图自编码器Graph Auto-Encoder: GAE，变分图自编码器 VGAE, SAGE。

3. 参数配置：

   • 对于 DeepWalk, Node2Vec，我们将窗口大小设为 10、随机游走序列长度为 80、每个节点开始的随机游走序列数量为 10。

   • 对于 GraRep，我们设定最大转移步长为 5 （即从一个节点最多经过 5 步转移到其它节点）。

   • 对于 LINE，我们将一阶embedding 和二阶 embedding 拼接起来作为最终 embedding 。

   • 所有方法的 embedding 维度为 200（LINE 的最终 embedding 维度为 200 + 200 = 400 ）。

   • 对于所有其它 baseline 方法，超参数配置都参考各自的原始论文。

   • 对于 DANE，为获得高阶邻近性矩阵 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ ，我们利用 Deep Walk 获取随机游走序列，然后使用大小为 10 的滑动窗口来构造高阶邻近性矩阵 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ 。我们并没有通过邻接矩阵 $\mathbf{E}$$\mathbf E$ 来直接计算 ${\mathbf{M}}^{(k)}$$\mathbf M^{(k)}$ ，因为直接计算的代价太大。

   • 对于 DANE，我们使用 LeakyReLU 作为激活函数。DANE 在四个数据集上采用不同的体系结构，如下表所示。对于每个数据集，第一行对应于网络拓扑结构的体系结构，第二行对应于节点属性的体系结构。这里我们仅给出编码器的体系结构，解码器的体系结构为编码器结构的翻转。

     

4. 节点分类任务：我们首先使用不同的模型在数据集上通过无监督训练节点的 embedding，然后对学到的节点 embedding 进行节点分类任务。

   我们使用 $L_2$$L_2$ 正则化的逻辑回归作为分类器。为进行全面的评估，我们分别随机选择 {10%,30%,50%} 的节点作为训练集，剩余节点作为测试集。对于随机选择的训练集，我们使用五折交叉验证来训练分类器，然后在测试集中评估分类性能，评估指标为 Micro-F1 和 Macro-F1 。

   不同embedding 方法的分类性能如下表所示，结论：

   • 与普通网络embedding 方法相比，DANE 取得显著提升。

   • 与属性网络embedding 方法相比，DANE 大多数都效果更好。

   

   

5. 节点聚类任务：为展示DANE 在无监督任务上的性能，我们对学到的节点embedding 进行聚类。这里我们采用k-means 聚类方法，并使用聚类准确率（利用标签信息来评估）作为评估指标。评估结果如下。结论：大多数情况下，DANE 具有更好的聚类效果。

   

6. 网络可视化：为进一步展示DANE 的效果，我们使用 t-SNE 可视化节点的embedding。我们仅给出 Cora 数据集的三种代表性 baseline 的结果。可以看到，和其它方法相比，DANE 可以实现更紧凑、间隔更好的类簇。因此，我们的方法可以在有监督任务和无监督任务上实现更好的性能。

   

7. 为评估采样策略的效果，我们将最负采样策略和其它两种替代方法进行比较：

   • 第一种为随机采样策略 DANE-RS，此时负样本为随机采样得到。

   • 第二种为重要性采样策略DANE-IS，此时负样本采样概率为：

     $$p_i(j)=\frac{\exp (-Q_{i,j})}{\sum _j\exp (-Q_{i,j})}$$

     其中 $\mathbf{Q}={\mathbf{H}}^{<M>}{\mathbf{H}}^{<X{>}^{\mathrm{\top }}}$$\mathbf Q = \mathbf H^{<M>} \mathbf H^{<X>^\top}$ ， $i$$i$ 为当前的节点（需要采样它的负样本）， $p_i(j)$$p_i(j)$ 表示 $j$$j$ 为负样本概率。

     直观而言，这种策略使得不相似的节点被采样为负样本的概率更大。

   我们分别使用这两种采样策略来学习节点的 embedding，然后在 Cora 数据集上进行节点分类。结果如下所示。结论：

   • DANE-RS 性能最差，因为它无法区分不同的负样本。

   • DANE-IS 效果更好，但是比最负采样策略更差。因为最负采样策略始终可以找到最负的样本。